public class MySinglelist {
    public Node head;//代表头节点
    public int length;//记录链表长度

    public int getLength() {
        return length;
    }

    class Node{
         public int val;//值
        public Node nextNode;//下一个节点的地址

         public Node(int val) {
             this.val = val;
         }

     }
     //创建单链表
    public void createList(){
         Node node1 = new Node(1);
         Node node2 = new Node(2);
         Node node3 = new Node(3);
         Node node4 = new Node(6);
         Node node5 = new Node(3);
         head = node1;
         node1.nextNode=node2;
         node2.nextNode=node3;
         node3.nextNode=node4;
         node4.nextNode=node5;
     }
     //遍历单链表
     public void displayList(MySinglelist list){
         Node cur = list.head;
         while(cur!=null){
             System.out.println(cur.val);
             cur=cur.nextNode;
         }
     }
    //判断链表中是否存在某一元素
    public boolean contains(int key) {
        Node cur = head;
        while (cur!=null) {
            if(cur.val==key){
                return true;
            }
            cur = cur.nextNode;
        }
        return false;
    }
    //头插法插入元素
    public boolean headInsert(int key,int val) {

        if (!contains(key)) {
            return false;
        } else {
            Node node = new Node(val);
            node.nextNode = head;//原头节点变为新节点的next Node
            head = node;//新节点变头节点
            length++;//长度更新
            return true;
        }
    }
    //尾插法插入元素
   public boolean lastInsert(int key,int val){
       if (!contains(key)) {
           return false;
       }else {
           Node currentNode = head;
           //找到要插入的位置的前一个元素；
           if(head.val ==key ){
               Node hnode = new Node(val);
               hnode.nextNode = head.nextNode;
               head.nextNode = hnode;
               length++;
               return true;
           }
           while ((currentNode.nextNode.val != key)) {
               currentNode = currentNode.nextNode;
           }
           if (head == null){
               return false;
           }else {
               Node node = new Node(val);
               node.nextNode = currentNode.nextNode.nextNode;//将需要插入的位置的下一个结点赋值为新节点的nextNode
               currentNode.nextNode.nextNode = node;//新节点变为需要插入位置的下一个结点
               length++;//长度更新
               return true;
           }
       }
   }
   //找到值为key的节点
   private Node searchPrev(int key) {
        if (head==null){
            return null;
        }
       Node cur = head;
       while (cur.nextNode != null) {
           if (cur.nextNode.val == key) {
               return cur;
           }
           cur = cur.nextNode;
       }
       return null;//没有找到
   }
   //删除元素
   public int delNode(int val){
        if(head.val==val){
            head=head.nextNode;
            return val;
        }
        Node cur = searchPrev(val);//找到val的前一个结点
       if (cur!=null) {
           Node del = cur.nextNode;//要删除的结点
           cur.nextNode = del.nextNode;
           return del.val;
       }else {
           return -1;
       }
   }
   //删除多个符合要求的元素
    public void delNodes(int val){
    if(head == null){
        return ;
    }
    Node prev = head;
    Node cur = head.nextNode;
    while(cur!=null){
        if(cur.val == val){
            prev.nextNode = cur.nextNode;
            cur = cur.nextNode;
        }else{
            prev = cur;
            cur = cur.nextNode;
        }
    }
    }
}